
\documentclass[11pt]{article}
\newtheorem{define}{Definition}
%\newcommand{\F}{{\mathbb{F}}}
%\usepackage{psfig}
\usepackage{amsmath,amssymb,amsfonts}
\usepackage{fullpage, color}
\usepackage{algpseudocode}
\usepackage{algorithm}
\oddsidemargin=0.15in
\evensidemargin=0.15in
\topmargin=-.5in
\textheight=9in
\textwidth=6.25in


\begin{document}
\input{preamble.tex}
\newcommand{\eps}{\epsilon}


%{lecture number}{lecture date}{Elena Grigorescu}{Your name}
\lecture{8}{September 13, 2012}{Elena Grigorescu}{Vivek Patel}

%%%% body goes in here %%%%

\section{Introduction}

Recall that in previous lectures we've seen a couple of examples of testable graph properties.
Our goal in this  lecture shall be to analyze the testability of some non-graph properties. We will look at properties of lists of real numbers, namely at the property of being sorted (say, in non-decreasing order). In the end we will mention how the ideas here extend to testing monotonicity of functions defined over some discrete domain (say $f:\{0,1\}^n\rightarrow \{0,1\}$). 

The aim here is to show a test which takes time $O(\log n)$ and decides whether the list is correctly sorted or it far from sorted (meaning that many of the entries of the list need to be modified in order to obtain a sorted list).

In practice one could use a quick test like this one to check if it is worth running some sorting algorithm on the data(in some applications, few outliers would not be that bad, but if there is a large fraction of outliers than one should resort). In such applications, if there are only few outliers then running  a very fast test would save the effort of running a typical sorting algorithm of super-linear complexity.


Example: Say we have a list of $n$ integers \{ 1,2,5,1,0,1...20 \}.
An efficient sorting algorithm like Quick sort would take $O(n \log n)$ time to sort the list, but if there are fewer than $.1\%$ elements that are out of order we might not care and do not need to sort.  We would like to have a test which
can test if the given list is sorted in time much smaller than linear.

\section{Reviewing the `Witness lemma'}

 We've seen the next lemma many times already (the upper bound part) and we used the lower bound in the previous lecture, but we recall it here again as we will be using it a few times today. 


\begin{lemma}[{Witness Lemma}]


\begin{enumerate}

\item (upper bound) If a test $T$ is s.t. $\Pr[T \mbox{finds witness}]=p<2/3, $  then if the test $T'$ is obtained by running   $T$ for $s=2/p$ times we have
 \[  Pr\mbox{[T' finds witness]} >  \frac{2}{3}\]

\item(lower bound)
If test $T''$ runs $T$ for $s<1/(2p)$ times then the 
\[  Pr\mbox{[T'' catches witness]} <  \frac{2}{3}\]

\end{enumerate}
\end{lemma}
\begin{proof}
  Since $Pr[\mbox{T catches witness}] = p$ we have 
  $\Pr[\mbox{T' does  not find a witness in any of its "s" steps}] =(1-p)^s$.
Since $ (1-p) < e^{-p}$, raising both sides to the power of $s$ we get
$(1-p)^{s} < e^{ -p . \frac{2}{p}}$ = $e^{-2} < \frac{1}{3}$. 

To show the second part, 
 we use $(1-p) \geq e^{-2p}$, if $0\leq p \leq \frac{3}{4}$.
As $ \frac{3}{4} > \frac{2}{3}$, 
\begin{eqnarray}
\Pr[\mbox{T'' does  not find a witness in any of its "s" steps}]&=&(1-p)^{s}\\ &>& e^{ -2p . \frac{1}{2p}} = e^{-1} > \frac{1}{3}.
\end{eqnarray}

\end{proof}

We use the lemma to analyze the query complexity of our algorithms. The upper bound says that $2/p$ queries are enough, and the lower bound says that $1/(2p)=\Omega(1/p)$ queries are neccessary to get the correct answer w.p. $>2/3$.


\section{Some simple tests  with high query complexity}

Recall that we are looking for a test for sortedness. The next two tests are natural but we'll see that they require  a linear number of queries.

\subsection{Test 1}

Consider the following test

\begin{algorithm}[H]
\caption{Consecutive pair sort testing}
\label{consecutive1}
\begin{algorithmic}
\State Input: A list of $n$ numbers, represented as $L=\langle \ell(1), \ell(2),\ldots, \ell(n)\rangle$ (where $\ell:[n]\rightarrow R$ represents labels of the indices) 
\State Pick an index $i$ which chosen uniformly from $[n]$
\State if $\ell(i) >  \ell(i+1)$ then reject
\State else accept
\end{algorithmic}
\end{algorithm}


Why is this a bad test? Clearly if it is given as input a sorted list the test always accepts. But what if it is given a list that is far from sorted? Does it detect a violating consecutive pair on any list with many outliers? 

We'll show that there is a list that is far from sorted yet the test only detects a consecutive unsorted pair with very small probability, and so it needs to make many queries to boost this probability to $2/3$.


Example: $L=\langle \frac n2,\frac n2 +1, \frac n2+2 \ldots n,1,2,3,.......n/2 \rangle$

Then the list is very far from being sorted: $dist(L, sortedness)=\frac{1}{2}$,  as we would need to completely modify either the fist half or the second half to get to a list that is fully sorted.


Analyzing the test above, we get $\Pr[\mbox{test rejects}]= \frac{1}{n-1}$.
Hence, by the witness lemma above, the number of queries required in order to catch a violating witness with probability $\frac{2}{3}$ is $(n-1)/2 = \Omega (n)$ which is too much.

\subsection{Test2}



\begin{algorithm}[H]
\caption{Random index sort testing}
\label{consecutive1}
\begin{algorithmic}
\State Input: A list of $n$ numbers, represented as $L=\langle \ell(1), \ell(2),\ldots, \ell(n)\rangle$ 
\State Pick indices $i<j$  which are chosen uniformly from  $[n]$.
\State if $\ell(i)> \ell(j)$ then reject
\State else accept
\end{algorithmic}
\end{algorithm}

\noindent
As before, we'll find a string that is far from sorted yet the test is unable to find a violating pair except with some small probability.

Example: A list that interleaves two sorted lists: $L=\langle {\bf 1},0,{\bf 2},1,{\bf 3},2,{\bf 4},3, ....\rangle$.

Note that $dist(L,sortedness)=\frac{1}{2}$ since among each consecutive pair of numbers $(2i+1, 2i+2)$ one of the labels need to be changed to get a non-decreasing sequence.

We have
\begin{eqnarray}
\Pr[ \mbox{ test rejects }]&=& \frac{ \# \mbox{ pairs } i<j \mbox{ with } \ell(i)>\ell(j)}{\#  \mbox{ pairs } i,j}\\
&=&\frac{\frac{n}{2}}{\binom{n}{2}} = \frac{1}{n-1}.
\end{eqnarray}
(where we used that index $2i+1$ is out of order only with index $2i+2$.) 
Hence again we need $\Omega (n)$ queries.

\section{A good test}
In this section we'll show a test that works with only $O(\log n)$ queries.

\begin{theorem}\label{thm:test}
There exists a test that given $\epsilon$, can test if a list of size $n$  is sorted by making only $O(\frac{\log n}{\epsilon})$ queries.
\end{theorem}

The Idea: View the $n$ indices of the list as  vertices of a directed line $L_n$, with edges directed from vertex $i$ to $i+1$, for $i\in [n-1]$. We'll add `shortcut' edges between some pairs $(i, j)$ (from $i$ to $j$, if $i<j$) which will decrease the distance between vertices. After the addition of the set of shortcuts we get a new graph $H$ with the following properties:

\begin{enumerate}  
\item  The number of edges in H is $n \log n$
\item  For any indices $i<j$ we have a directed path of length at most $2$  between them in $H$.
\end{enumerate}
Such a graph is called a $2$-{\em transitive closure (TC) spanner.}

\subsection{How to build $H$}

The graph $H$ we get from the previous stage has $n$ nodes. Pick the mid- point $v_{mid}=\frac{n}{2}$ and mark it on the graph . For every vertex to the left of the 
mid point add a directed edge connecting that vertex to the mid point. For every vertex to the right of the midpoint add a directed edge from
the mid point  to it. Hence the distance between any vertex $i<v_{mid}$ and $j>v_{mid}$  is at most $2$. We then do this recursively on the segments to the left and to the right of the mid point.
Therefore, $\forall i,j $ there exists a level of recursion when $i$ and $j$ are separated by a midpoint at that level. Then  both $i,j$ are connected to the midpoint at that level and so they are within distance $2$ from each other. This concludes that $H$ is a TC-spanner.
Finally, counting the number of edges of the graph $H$, note that  Level 1 of recursion we add at most $n$
edges. Similarly, at each other level we add at most $n$ more edges. Since there are $\log n$ levels, we added at most $n \log n$ edges to obtain $H$.  
 
 \subsection{The test}

\begin{algorithm}[H]
\caption{Test 3}
\label{consecutive1}
\begin{algorithmic}
\State Input: A list of $n$ numbers, represented as $L=\langle \ell(1), \ell(2),\ldots, \ell(n)\rangle$
\State Pick an edge $(i,j)$ (where $i<j$) uniformly from $H$ 
\State if $\ell(i) > \ell(j)$ reject
\State else accept
\end{algorithmic}
\end{algorithm}

We'll next analyze this test.




Suppose list is $\eps$-far from sorted.
Call an edge {\em bad} if $i<j$, but $\ell(i)>\ell(j).$
Then $\Pr[\text{ test }\ref{consecutive1} \text{ finds a bad edge}]=\frac{\#\text{ bad edges}}{|H|}$. 

In what follows we'll count the number of bad edges is $H$.

\begin{lemma}\label{lem:eds}
The number of bad edges in $H$ is $\geq$ $\frac{\eps}{2} n.$
\end{lemma}

Notice that Lemma \ref{lem:eds} immediately implies Theorem \ref{thm:test}, since $|H|=n\log n$ and so it is enough to run the basic test $O(\log n/\eps)$ times to find a bad edge w.p. $2/3$. 

\begin{proof}[of Lemma\ref{lem:eds}]
Call a {\em bad vertex} one that is adjacent to a bad edge. Otherwise we call it a {\em good vertex.}

We make use of 2 more claims to prove the lemma.

\begin{claim}\label{cl1}
The good vertices are already sorted.
\end{claim}

\begin{claim}\label{cl2} If set $S\in [n]$ is sorted then it is enough to change $n-|S|$ labels in order to get a sorted List.
\end{claim}

We can now complete the proof of the lemma using the claims. Recall that at least $\eps n$ labels need to be changed to get a sorted list.
By claim \ref{cl1} all good vertices are ordered, and by Claim \ref{cl2}  it is enough to change the labels of the bad vertices to get a sorted list.
This implies that the number of bad vertices must be $\geq \eps n$
Since a bad edge is adjacent to at most 2 bad vertices there must be at least  $\frac{\eps}{2} n$ bad edges.

It remains to prove the claims.

\begin{proof}[of Claim\ref{cl1}]  We need to show that if $i<j$ then $\ell(i)<\ell(j).$   Since $H$ is a $2$- TC Spanner 
$i,j$ are at a distance of at most $2$ in $H$. 
If the distance is $1$, that is $(i,j)$ is an edge, since both  $i,j$ are good then we must have $\ell(i)<\ell(j)$.
If the distance between $i$ $j$ is $2$, then we must have the path as $(i,k)(k,j)$ in $H$. Again it must be that both the edges are good, so we have $\ell(i)\leq\ell(k)$ and $\ell(k)\leq \ell(j)$ hence we have $\ell(i)<\ell(j).$
\end{proof}

\begin{proof}[of Claim \ref{cl2}] 
Notice that we can relabel the bad vertices to take the value of the closest good vertex and obtain an ordered list.
\end{proof}
 
\end{proof}


\section{Testing monotonicity of functions}

The above test can be viewed as a test for the monotonicity of a function defined over the domain $L_n$ and range $R$. One can generalize this to other  discrete domains. For example, a well studied property is monotonicity of functions defined over the hypercube $\{0,1\}^n$, that is, given a function $f:\{0,1\}^n\rightarrow \{0,1\}$ is it monotone or far from any monotone function? Here the partial order on $\{0,1\}^n$ is given by set inclusion. 

\end{document}




